Loading [MathJax]/jax/output/CommonHTML/jax.js
Title Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries
January 29, 2025 (GHC 8102)

Abstract: The dictionary problem involves maintaining a set S[U] of n keys under insertions, deletions, and membership queries focusing on efficiency in both time and space. This fundamental problem has been studied extensively for six decades since 1953. Recently, a series of works has established the optimal time-space trade-off for dictionaries. In this talk, I will describe the tight lower bound result that any dictionary with an operational time t must incur a redundant Ω(log(t)n) bits per key in space.